class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        result = []
        r = [0] * 10001
        intervals_len = len(intervals)
        for i in range(intervals_len):
            interval = intervals[i]
            color = max([r[interval[0]], r[interval[1]]])
            if color == 0:
                color = i + 1
            if r[interval[0]] > 0 and r[interval[0]] != color:
                fcolor = r[interval[0]]
                fp = interval[0]
                while fp >= 0 and r[fp] == fcolor:
                    r[fp] = color
                    fp -= 1
            if r[interval[1]] > 0 and r[interval[1]] != color:
                fcolor = r[interval[1]]
                bp = interval[1]
                while bp < len(r) and r[bp] == fcolor:
                    r[bp] = color
                    bp += 1
            for j in range(interval[0], interval[1]+1):
                r[j] = color
        hp, tp = 0, 0
        while tp < len(r):
            while hp < len(r) and r[hp] == 0:
                hp += 1
            if hp >= len(r):
                break
            color = r[hp]
            tp = hp
            while tp < len(r) and r[tp] == color:
                tp += 1
            result.append([hp, tp-1])
            hp = tp
        return result

s = Solution()
intervals = [[1,3],[2,6],[8,10],[15,18]]
result = s.merge(intervals)
print(result)

intervals = [[1,4],[4,5]]
result = s.merge(intervals)
print(result)

intervals = [[1,4],[5,6]]
result = s.merge(intervals)
print(result)

intervals = [[2,3],[0,1],[1,2],[3,4],[4,5],[1,1],[0,1],[4,6],[5,7],[1,1],[3,5]]
result = s.merge(intervals)
print(result)
